package com.startx.http.system.tool;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;

import org.springframework.util.StringUtils;

import com.google.common.collect.Lists;

/**
 * 抽奖工具类
 * @author minghu.zhang
 */
public final class AliasMethod {
    /* The random number generator used to sample from the distribution. */
    private final Random random;
 
    /* The probability and alias tables. */
    private final int[] alias;
    private final double[] probability;
   	/**
   	 * 礼品列表
   	 */
   	private List<Integer> gifts = Lists.newArrayList();
 
    /**
     * Constructs a new AliasMethod to sample from a discrete distribution and
     * hand back outcomes based on the probability distribution.
     * <p/>
     * Given as input a list of probabilities corresponding to outcomes 0, 1,
     * ..., n - 1, this constructor creates the probability and alias tables
     * needed to efficiently sample from this distribution.
     *
     * @param probabilities The list of probabilities.
     */
    public AliasMethod(List<Double> probabilities) {
        this(probabilities, new Random());
    }
 
    /**
     * Constructs a new AliasMethod to sample from a discrete distribution and
     * hand back outcomes based on the probability distribution.
     * <p/>
     * Given as input a list of probabilities corresponding to outcomes 0, 1,
     * ..., n - 1, along with the random number generator that should be used
     * as the underlying generator, this constructor creates the probability
     * and alias tables needed to efficiently sample from this distribution.
     *
     * @param probabilities The list of probabilities.
     * @param random        The random number generator
     */
    public AliasMethod(List<Double> probabilities, Random random) {
        /* Begin by doing basic structural checks on the inputs. */
        if (probabilities == null || random == null)
            throw new NullPointerException();
        if (probabilities.size() == 0)
            throw new IllegalArgumentException("Probability vector must be nonempty.");
 
        /* Allocate space for the probability and alias tables. */
        probability = new double[probabilities.size()];
        alias = new int[probabilities.size()];
 
        /* Store the underlying generator. */
        this.random = random;
 
        /* Compute the average probability and cache it for later use. */
        final double average = 1.0 / probabilities.size();
 
        /* Make a copy of the probabilities list, since we will be making
         * changes to it.
         */
        probabilities = new ArrayList<Double>(probabilities);
 
        /* Create two stacks to act as worklists as we populate the tables. */
        Deque<Integer> small = new ArrayDeque<Integer>();
        Deque<Integer> large = new ArrayDeque<Integer>();
 
        /* Populate the stacks with the input probabilities. */
        for (int i = 0; i < probabilities.size(); ++i) {
            /* If the probability is below the average probability, then we add
             * it to the small list; otherwise we add it to the large list.
             */
            if (probabilities.get(i) >= average)
                large.add(i);
            else
                small.add(i);
        }
 
        /* As a note: in the mathematical specification of the algorithm, we
         * will always exhaust the small list before the big list.  However,
         * due to floating point inaccuracies, this is not necessarily true.
         * Consequently, this inner loop (which tries to pair small and large
         * elements) will have to check that both lists aren't empty.
         */
        while (!small.isEmpty() && !large.isEmpty()) {
            /* Get the index of the small and the large probabilities. */
            int less = small.removeLast();
            int more = large.removeLast();
 
            /* These probabilities have not yet been scaled up to be such that
             * 1/n is given weight 1.0.  We do this here instead.
             */
            probability[less] = probabilities.get(less) * probabilities.size();
            alias[less] = more;
 
            /* Decrease the probability of the larger one by the appropriate
             * amount.
             */
            probabilities.set(more,
                    (probabilities.get(more) + probabilities.get(less)) - average);
 
            /* If the new probability is less than the average, add it into the
             * small list; otherwise add it to the large list.
             */
            if (probabilities.get(more) >= 1.0 / probabilities.size())
                large.add(more);
            else
                small.add(more);
        }
 
        /* At this point, everything is in one list, which means that the
         * remaining probabilities should all be 1/n.  Based on this, set them
         * appropriately.  Due to numerical issues, we can't be sure which
         * stack will hold the entries, so we empty both.
         */
        while (!small.isEmpty())
            probability[small.removeLast()] = 1.0;
        while (!large.isEmpty())
            probability[large.removeLast()] = 1.0;
    }
 
    /**
     * Samples a value from the underlying distribution.
     *
     * @return A random value sampled from the underlying distribution.
     */
    public int next() {
        /* Generate a fair die roll to determine which column to inspect. */
        int column = random.nextInt(probability.length);
 
        /* Generate a biased coin toss to determine which option to pick. */
        boolean coinToss = random.nextDouble() < probability[column];
 
        /* Based on the outcome, return either the column or its alias. */
       /* Log.i("1234","column="+column);
        Log.i("1234","coinToss="+coinToss);
        Log.i("1234","alias[column]="+coinToss);*/
        return coinToss ? column : alias[column];
    }
    
   	/**
   	 * 初始化
   	 * @return
   	 */
    public static AliasMethod newInstance(String doprize) {
    	List<Surprize> surprizeList = Lists.newArrayList();
    	String[] prizesAndWeight = doprize.replace(" ", "").split(";");
		
		double total = 0;
		for (String prizeWeight : prizesAndWeight) {
			if (StringUtils.isEmpty(prizeWeight)) {
				continue;
			}
			String[] ps = prizeWeight.split(",");
			int prize = Integer.parseInt(ps[0]);
			int weight = Integer.parseInt(ps[1]);
			Surprize surpize = new Surprize();
			
			surpize.setPrize(prize);
			surpize.setWeight(weight);
			
			surprizeList.add(surpize);
			
			total += weight;
		}
		
		TreeMap<Integer, Double> map = new TreeMap<Integer, Double>();
	 
		for(Surprize surprize:surprizeList) {
			map.put(surprize.getPrize(), surprize.getWeight()/total);
		}
		
		AliasMethod method = new AliasMethod(new ArrayList<Double>(map.values()));
	    method.addAllGifts(method,map.keySet());
	    
		return method;
    }
    
    /**
     * 添加物品到Alias
     * @param keySet
     */
    private void addAllGifts(AliasMethod method,Set<Integer> gifts) {
    	method.getGifts().addAll(gifts);
	}
    
    /**
     * 获取所有的奖品
     * @return
     */
    public List<Integer> getGifts() {
    	return gifts;
    }

    /**
     * 随机抽取一个物品
     * @param method
     * @return
     */
	public int get() {
    	
    	int index = this.next();
        int key = gifts.get(index);
        
        return key;
    }
    
    /**
	 * 超级惊喜
	 */
	public static class Surprize {
		
		private int prize;
		private int weight;
		private double prob;

		public int getPrize() {
			return prize;
		}

		public void setPrize(int prize) {
			this.prize = prize;
		}

		public int getWeight() {
			return weight;
		}

		public void setWeight(int weight) {
			this.weight = weight;
		}

		public double getProb() {
			return prob;
		}

		public void setProb(double prob) {
			this.prob = prob;
		}

		@Override
		public String toString() {
			return "[prize=" + prize + ", weight=" + weight + ", prob=" + prob + "]\n";
		}
	}
}
